package scu.maqiang.cg;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

import scu.maqiang.numeric.CG;
import scu.maqiang.numeric.Constants;
import scu.maqiang.numeric.MVO;

/**
 * 计算二维凸包类，给出一系列二维坐标点, 计算出凸包所构成的点集合
 * 
 * @author 马强
 *
 */
public class ConvexHull {

	public static void main(String[] args) {
		/*
		int[][] x = { { 200, 400 }, { 300, 500 }, { 300, 300 }, { 400, 300 }, { 400, 400 }, { 500, 500 }, { 500, 200 },
				{ 350, 200 }, { 200, 200 } };
		int[] result = getCH1(x);
		System.out.println("Ordered points: ");
		System.out.println(MVO.toString(x));
		System.out.println("ConvexHull Indices: ");
		System.out.println(Arrays.toString(result));
		
		System.out.println("=======================\n");
		int[][] x1 = {{0, 0}, {1, 0}, {2, 0}, {1, 1}, {0, 2}, {0, 1}};
		result = getCH1(x1);
		System.out.println("Ordered points: ");
		System.out.println(MVO.toString(x1));
		System.out.println("ConvexHull Indices: ");
		System.out.println(Arrays.toString(result));*/
		/*double[][] x = { { 200, 400 }, { 300, 500 }, { 300, 300 }, { 400, 300 }, { 400, 400 }, { 500, 500 }, { 500, 200 },
				{ 350, 200 }, { 200, 200 } };*/
		double[][] x = {{1.0, 0.0}, {0.5, 0.5}, {0.6, 0.7}, {0.2, 0.8}, {0.0, 0.5}, {0.0, 0.0}};
		double[][] CH = GrahamScan(x);
		System.out.println(MVO.toString(CH));
		
		double[][] x2 = { { 200, 400 }, { 300, 400 }, { 300, 300 }, { 400, 300 }, { 400, 400 }, { 500, 400 }, { 500, 200 },
				{ 350, 200 }, { 200, 200 } };
		double[][] CH2 = GrahamScan(x2);
		System.out.println(MVO.toString(CH2));
		
	}

	/**
	 * 使用卷包裹法计算平面一组点的凸包
	 * @param x 平面点数组, 行数表示结点个数, 列数为2，分别存储点的x坐标与y坐标, 最后返回以x坐标升序排列的点, 如果x坐标相同， 则以y坐标升序排列
	 * @return 得到凸包所包含的点在排序后的点数组中的索引值, 起始索引与最末索引相同
	 */
	public static int[] getCH1(int[][] x) {
		Arrays.sort(x, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
		//System.out.println(MVO.toString(x));
		int n = x.length;
		int[] ans = new int[n];
		int[] sta = new int[n];
		int cnt = 0;
		int tail = 2;
		sta[0] = 0;
		sta[1] = 1;
		for (int i = 2; i < n; i++) {
			while(tail > 1 && ! (CG.area2DT3(x[sta[tail - 2]], x[sta[tail - 1]], x[i]) > 0)) {
				tail--;
			}
			sta[tail++] = i;
/*				
			while(CG.area2DT3(x[sta[tail - 2]], x[sta[tail - 1]], x[i]) <= 0) {
				tail--;
				if (tail <= 1) {
					break;
				}
			}
			sta[tail++] = i;
*/
		}
		
//		System.out.println(Arrays.toString(sta));
		
		//凸包下半部分的点索引
		for(int i = 0; i < tail; i++) {
			ans[cnt++] = sta[i];
		}
		
		
		Arrays.fill(sta, 0);
		sta[0] = n - 1;
		sta[1] = n - 2;
		tail = 2;
		for(int i = n - 3; i >= 0; i--) {
			while(tail > 1 && ! (CG.area2DT3(x[sta[tail - 2]], x[sta[tail - 1]], x[i]) > 0)) {
				tail--;
			}
			sta[tail++] = i;			
		}
		//凸包上半部分的点索引
		for(int i = 1; i < tail; i++) {
			ans[cnt++] = sta[i];
		}
//		System.out.println(Arrays.toString(ans));
//		System.out.println(cnt);
		int[] result = new int[cnt];
		for(int i = 0; i < cnt; i++) {
			result[i] = ans[i];
		}
		return result;
	}
	
	/**
	 * 使用卷包裹法计算平面一组点的凸包
	 * @param x 平面点数组, 行数表示结点个数, 列数为2，分别存储点的x坐标与y坐标, 最后返回以x坐标升序排列的点, 如果x坐标相同， 则以y坐标升序排列
	 * @return 得到凸包所包含的点在排序后的点数组中的索引值, 起始索引与最末索引相同
	 */
	public static int[] getCH1(double[][] x) {
		Comparator<double[]> comparator = (a, b) -> {
			if (Math.abs(a[1] - b[1]) < 1.0e-10) {
				if (a[0] > b[0]) {
					return 1;
				} else {
					return -1;
				}
			} else {
				if (a[1] > b[1]) {
					return 1;
				} else {
					return -1;
				}
			}
		};
		Arrays.sort(x, comparator) ;
		//System.out.println(MVO.toString(x));
		int n = x.length;
		int[] ans = new int[n];
		int[] sta = new int[n];
		int cnt = 0;
		int tail = 2;
		sta[0] = 0;
		sta[1] = 1;
		for (int i = 2; i < n; i++) {
			while(tail > 1 && ! (CG.area2DT3(x[sta[tail - 2]], x[sta[tail - 1]], x[i]) > 0)) {
				tail--;
			}
			sta[tail++] = i;
/*				
			while(CG.area2DT3(x[sta[tail - 2]], x[sta[tail - 1]], x[i]) <= 0) {
				tail--;
				if (tail <= 1) {
					break;
				}
			}
			sta[tail++] = i;
*/
		}
		
//		System.out.println(Arrays.toString(sta));
		
		//凸包下半部分的点索引
		for(int i = 0; i < tail; i++) {
			ans[cnt++] = sta[i];
		}
		
		
		Arrays.fill(sta, 0);
		sta[0] = n - 1;
		sta[1] = n - 2;
		tail = 2;
		for(int i = n - 3; i >= 0; i--) {
			while(tail > 1 && ! (CG.area2DT3(x[sta[tail - 2]], x[sta[tail - 1]], x[i]) > 0)) {
				tail--;
			}
			sta[tail++] = i;			
		}
		//凸包上半部分的点索引
		for(int i = 1; i < tail; i++) {
			ans[cnt++] = sta[i];
		}
//		System.out.println(Arrays.toString(ans));
//		System.out.println(cnt);
		int[] result = new int[cnt];
		for(int i = 0; i < cnt; i++) {
			result[i] = ans[i];
		}
		return result;
	}
	
	/**
	 * 使用GahamScan算法计算平面点集的凸包
	 * @param x 
	 * @return
	 */
/*	public int[] GrahamScan(double[][] x) {
		Arrays.sort(x, (a, b) -> a[1] == b[1] ? (int)(a[0] - b[0]) : (int)(a[1] - b[1]));
		return null;
	}
*/	
	/**
	 * 使用GrahamScan算法计算平面点集的凸包
	 * @param x 平面离散点坐标
	 * @return 凸包点序列
	 */
	public static double[][] GrahamScan(double[][] x) {
		int n = x.length;
		//1. 寻找最左端最底部的点作为闭包的第一个顶点
		double[] ltl = x[0];
		double[] temp = {0.0, 0.0};
		for(int i = 1; i < n; i++) {
			if(x[i][0] < ltl[0] || (Math.abs(x[i][0] - ltl[0]) < Constants.Er && x[i][1] < ltl[1])) {
				temp[0] = ltl[0];  temp[1] = ltl[1]; 
				ltl[0] = x[i][0];  ltl[1] = x[i][1];
				x[i][0] = temp[0]; x[i][1] = temp[1];
			}
		}
//		System.out.println(MVO.toString(x));
//		Arrays.sort(x, 1, n, (a, b) -> CG.area2DT3(x[0], a, b) > 0.0 ? -1:1);
		//2. 对所有点按相对于第一个点的辐角进行排序，若出现三点共线, 则x坐标较小的排前面
		Arrays.sort(x, 1, n, (a, b) -> {
			double area = CG.area2DT3(x[0], a, b);
			if(Math.abs(area) < Constants.Er) {
				return (a[0] < b[0])?-1:1;
			}
			return area > 0.0?-1:1;
		});
		//3.Graham扫描, 找出凸包点序列
		Stack<double[]> S = new Stack<>();
		Stack<double[]> T = new Stack<>();
		S.push(x[0]);
		S.push(x[1]);
		for(int i = n - 1; i >= 2; i--) {
			T.push(x[i]);
		}
		int n_S = 2;
		int n_T = n - 2;
		double[] S0, S1, T0;
		while(!T.empty()) {
			S0 = S.get(n_S - 2);
			S1 = S.get(n_S - 1);
			T0 = T.get(n_T - 1);
			double area = CG.area2DT3(S0, S1, T0);
			//如果扫描的三个点在一条直线上, 
			if(Math.abs(area) < Constants.Er) {
				S.pop();
				S.push(T.pop());
				n_T--;
				/*S.push(T.pop());
				n_S++;
				n_T--;*/
				continue;
			}
			if(area > 0.0) {
				S.push(T.pop());
				n_S++;
				n_T--;
			} else {
				S.pop();
				n_S--;
			}
		}
		double[][] result = new double[n_S][];
		for(int i = 0; i < n_S; i++) {
			result[i] = S.get(i);
		}
		return result;
	}

}
